package day_2022_4_to_7.nowcoder;

import java.util.HashMap;
import java.util.Map;

/**
 * 青蛙跳台阶
 * @author haomin
 * @date 2022/04/14 10:00
 **/
public class JumpFloor_7_8f {
    public int jumpFloor0(int target) {
        if(target == 1){
            return 1;
        }
        if(target == 2){
            return 2;
        }
        int[] dp = new int[target + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= target ; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        int num = dp[target];
        return num;
    }

    // 迭代
    public int jumpFloor1(int target) {
        if(target == 1){
            return 1;
        }
        if(target == 2){
            return 2;
        }
        int a = 1;
        int b = 2;
        int c = 0;
        for(int i = 3;i <= target; i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    // 递归
    public int jumpFloor2(int target) {
        if(target == 1){
            return 1;
        }
        if(target == 2){
            return 2;
        }
        return jumpFloor2(target -1) + jumpFloor2(target -2);
    }

    // 减枝
    private Map<Integer,Integer> filter = new HashMap<>();
    public int jumpFloor(int target) {
        if(target == 1){
            return 1;
        }
        if(target == 2){
            return 2;
        }

        int pre = 0;
        if(filter.containsKey(target - 1)){
            pre = filter.get(target - 1 );
        }else {
            pre = jumpFloor(target - 1);
            filter.put(target - 1,pre);
        }

        int ppre = 0;
        if(filter.containsKey(target - 2)){
            pre = filter.get(target - 2);
        }else {
            ppre = jumpFloor(target - 2);
            filter.put(target - 2,ppre);
        }

        return pre + ppre;
    }
}